package com.yan_jiu_sheng.LeetCodeHot100.AC;

/**
 * https://leetcode.cn/problems/find-the-duplicate-number/description/?envType=study-plan-v2&envId=top-100-liked
 * 参考通过 快慢指针
 *
 * @author yulongtian
 * @create 2024-07-26 16:09
 */
public class Test89 {
    public static void main(String[] args) {
        int[] nums = {3, 1, 3, 4, 2};
        System.out.println(new Test89().findDuplicate(nums));
    }

    /*
    有向有环图，找出入环口
     */
    public int findDuplicate(int[] nums) {
        int fast = nums[0];
        fast = nums[fast];
        int slow = nums[0];
        while (fast != slow) {
            fast = nums[fast];
            fast = nums[fast];
            slow = nums[slow];
        }
        slow = 0;
        while (fast != slow) {
            fast = nums[fast];
            slow = nums[slow];
        }

        return fast;
    }


//    /*
//    暴力方法超时
//     */
//    public int findDuplicate(int[] nums) {
//        int n = nums.length;// 1 ~ n-1
//        for (int i = 0; i < n; i++) {
//            for (int j = i + 1; j < n; j++) {
//                if (nums[i] == nums[j]) {
//                    return nums[i];
//                }
//            }
//        }
//
//        return nums[0];
//    }

}
